package task1;

import java.util.Scanner;

public class work7_1 {
    public static void main(String[] args) {//素数筛计算n以内的素数个数
//        int n= (int)1e8;
//        long start=System.currentTimeMillis();
//       /* System.out.println("共计:"+countPrimesAs(n)+"个\n耗时"+(System.currentTimeMillis()-start)+"ms");*/
        System.out.println(countPrimesAs(new Scanner(System.in).nextInt()));
    }

    /*public static int countPrimesOl(int n)//欧拉筛法
    {
      if(n<2) return 0;

      boolean[] num=new boolean[n];
      int[] prime=new int[n];
      int count=0;

      for(int i=2;i<n;i++)
      {
          if(!num[i]){
              prime[count++]=i;
          }
          for(int j=0;j<count&&prime[j]*i<n;j++){
              num[prime[j]*i]=true;
              if(i%prime[j]==0)break;
          }
      }
      return count;
    }*/

    public static int  countPrimesAs(int n)
    {
        if (n<2) return 0;
        boolean[] num=new boolean[n+1];//只需要判断个数，布尔数组效率更高
        for(int i=2;i<=Math.sqrt(n);i++)//只需要筛选到根号n即可,
            if(!num[i])//若一个数是素数，则开始筛选
                for(int j=i*i;j<=n;j+=i)
                    num[j]=true;

        int count=0;
        /*for(boolean isPrime:num)
            if(!isPrime)
                count++;*/
        for(int i=0;i<num.length;i++)
        {
            if(!num[i]){
                count++;
                System.out.println(i);
            }
        }

        return count-2;
    }

}
